This invention relates to an error-detecting encoding and decoding apparatus and to a dividing apparatus. More particularly, the invention relates to an error-detecting encoding apparatus for generating parity bits for detecting error in an input data string and appending the parity bits to the data string, an error-detecting decoding apparatus for applying error-detecting processing to an input data string to which parity bits have been appended and detecting error in the input data string, and a dividing apparatus that can be used in this error-detecting encoding and decoding apparatus.
An error-detecting code is applied in a system in which it is required that data be transmitted without error when data communication is carried out, as in the case of mobile communications, facsimile machines and cash dispensers at banks, etc., or in a system in which it is required that data be read out without error when a large quantity of data is stored on a magnetic disk or CD. Further, an error-detecting code usually is used in conjunction with an error-correcting code and is for performing detection of an error that could not be correctly completely by error correction; if error is detected, resend control or re-readout control is, performed.                System in Which Error Correction is Applied        
FIG. 42 is an example of the configuration of a system in which error correction is applied. On a transmitting side 1, an error-detecting encoder 1b applies error-detecting encoding to a data string of prescribed bit length generated by an information generator 1a, and an error-correcting encoder 1c subjects the input data string to error-correcting encoding by convolutional encoding or turbo encoding processing and transmits the encoded data to a receiving side 3. On the receiving side 3, an error-correcting decoder 3a decodes the entered encoded data string by error-correcting decoding and inputs the decoded data string to an error-detecting decoder 3b. The latter applies error-detecting decoding to the decoded data string to thereby detect whether error is present or not and, if an error is present, sends a resend-request signal RRQ to the transmitting side. If there is no error, an information extracting unit 3c extracts and outputs the data. Described below will be a CRC (Cyclic Redundancy Check), which is error detection based upon a cyclic code.                CRC        
Simply stated, on the transmitting side, CRC regards a data string of a prescribed bit length as a polynomial, divides the data string by a polynomial (a generator polynomial) that is for generating an error-detecting code, and performs encoding in such a manner that the remainder will become zero. On the receiving side, CRC regards a receive data string as a polynomial, divides this data string by the same generator polynomial as that on the transmitting side, judges that there is no error if the remainder is zero and judges that there is an error if the remainder is not zero.
Specifically, on the transmitting side, k-bit information is regarded as a polynomial K(x), the polynomial K(x) is divided by a generator polynomial G(x), and a parity bit is appended in such a manner that the remainder will be zero. For example, if the generator polynomial G(x) consists of 16 bits andx16K(x)÷G(x)=Q(x), remainder R(x)holds, thenW(x)=x16K(x)+R(x)is adopted as is adopted as a code word. Here x16K(x) signifies a data string in which 16 “0” bits have been appended to the low-order side of the k-bit data string.
On the receiving side, if W′(x)=W(x)+E(x), which is the result of appending an error E(x) to the code word W(x), is received, then W′(x) is divided by G(x). Absence of error is detected if the remainder is zero. If the remainder is other than zero, then the presence of an error is detected. More specifically,W′(x)/G(x)is calculated and whether the above is divisible is detected.
Next, a case where a 32-bit signal of all “1”s is subjected to error-detecting encoding and decoding by a generator polynomial G(x)=x16+x12+x5+1 will be illustrated.                CRC Calculating Unit        
FIG. 43 illustrates first and second examples of structures of a CRC calculating unit in a case where generator polynomial G(x)=x16+x12+x5+1 holds.
{circle around (1)} First CRC Calculating Unit
(A) of FIG. 43 illustrates an example of an ordinary CRC calculating unit, namely a divider for when G(x)=x16+x12+x5+1 holds. The CRC calculating unit is constituted by a 16-stage shift register SR, exclusive-OR gates EOR1 to EOR3, which are provided on the input side at positions of bits and 0, 5 and 12, for performing an exclusive-OR operation between the output data of the preceding stage and feedback data, and a switch SW provided on the output side at the position of bit 15.
The data string x16K(x) can be divided by inputting the data string to the EOR1 one bit at a time from the higher order side in a state in which the switch has been changed over to the feedback side (the A side). That is, in error-detecting encoding, if the data string K(x) prior to encoding is assumed to be 32 bits, then x16K(x) becomes 48 bits. This 48-bit data string is input from the higher order side while causing the shift register SR to operate. The content of the shift register SR when the input of the 48 bits ends is the remainder R(x) and therefore this is appended to the lower order side of K(x) as the parity bits and the result is output as W(x).
If W′(x) is 48 bits when error-detecting decoding is performed, the 48-bit signal is input to the EOR1 of a CRC calculating unit, the structure of which is identical with that shown in (A) of FIG. 43, from the higher order side while the shift register SR is made operate. The content of the shift register SR when the input of the 48 bits ends is the remainder R(x) and therefore absence of an error is decided if all bits are “0”s and presence of an error is decided if even a single bit is not “0”.
{circle around (2)} Second CRC Calculating Unit
(B) of FIG. 43 illustrates a CRC calculating unit [a divider when G(x)=x16+x12+x5+1 holds] in which the number of operations is reduced by modifying the data input position of (A). Here the position of the EOR1 for data input is moved from the left end to the right end. The data input is divided by inputting the data to the EOR1 one bit at a time from the higher order side of the data string in a manner similar to that of (A). As compared with (A), the position of EOR1 is merely moved from the left end to the right end, but this is equivalent to inputting the data while multiplying the input data string by x16. That is, if the 32-bit data string K(x) is input to the EOR1 from the higher order side while the shift register SR is made to operate, then the content of the shift register SR when the input of the 32-bit data string K(x) ends is the remainder R(x) and therefore this is appended to the lower order side of K(x) as the parity bits (16 bits). The result is output as W(x).
If the input data string W′(x) is composed of 48 bits with the inclusion of the parity bits (the 16 bits on the lower order side are the parity bits) when error-detecting decoding is performed, then 32 bits of the data string are input to the EOR1 of a CRC calculating unit, the structure of which is identical with that shown in (B) of FIG. 43, from the higher order side while the shift register SR is made operate. The content of the shift register SR when the input of the 32 bits ends is the remainder. Accordingly, the remainder is compared with the remaining 16 bits that are the parity bits, absence of an error is decided if there is perfect agreement and presence of an error is decided if there is not perfect agreement. As a result, the number of operations can be reduced to 32.
Error-detecting encoding can also be performed as follows: If the input data string W′(x) is composed of 48 bits with the inclusion of the parity bits (the 16 bits on the lower order side are the parity bits), then all 48 bits of the data string are input to the EOR1 of a CRC calculating unit, the structure of which is identical with that shown in (B) of FIG. 43, from the higher order side while the shift register SR is made to operate. In this case, absence of an error is decided if the content of the shift register SR is all “0”s and presence of an error is determined if the content is not all “0”s. It should be noted that the content of the shift register SR in this error-detecting decoding scheme is not the remainder but indicates the result of coincidence detection.                Prior-Art Example of Encoder        
In the CRC calculating unit shown in (B) of, the value in shift register SR is made all “0”s in the initial state. The switch SW is switched to the A side and the data string K(x) is input to the EOR1 successively one bit at a time. The register value R(x) when input of the entire data strings ends is the residue of G(x), namely the remainder. Accordingly, if the switch SW is switched to the B side and the value R(x) of the shift register SR is output, then parity bits can be obtained.
This illustrates an example in which a 32-bit data string K(x) of all “1”s is subjected to CRC encoding by the generator polynomial G(x)=x16+x12+x5+1. The bits of the value R(x) in the shift register SR when input of the 32 bits ends are the parity bits. In this case, K(x), x16K(x), R(x) and W(x) are as follows:K(x)=x31+x30+x29+x28+ . . . +x2+x1+1x16K(x)=x47+x46+x45+x44+ . . . +x18+x17+x16R(x)=x15+x12+x11+x8+x7+x6+x3+x2+x+1W(x)=x16K(x)+R(x)=(x47+x46+x45+x44+ . . . +x18+x17+x16)+(x15+x12+x11+x8+x7+x6+x3+x2+x+1)
FIG. 44 illustrates the content of the register SR when a data string whose 32 bits on the higher order side are all “1”s in the data string x16K(x) has been input to the EOR1 shown in (B) of FIG. 43 one bit at a time by one clock. The bits of the value R(x) in the shift register SR when input of the 32 bits ends are the parity bits.                First Prior-Art Example of Decoder (Coincidence-detecting Decoding Method)        
In the CRC calculating unit shown in (B) of FIG. 43, the value in the register SR is made all “0”s in the initial state. The switch SW is switched to the A side and only information bits obtained by excluding the parity bits in the input data string W(x)′ are input successively. Coincidence is detected between the value in the register SR when input only of the information bits ends and the parity bits, which are the remaining bits of the input data string. It is determined that there is no error if the two coincide and that there is an error if the two do not coincide.
FIG. 45 illustrates the content of the register SR when encoded data that is the result of appending 16 parity bits to a 32-bit data string of all “1”s has been input to the EOR1 shown in (B) of FIG. 43 from the higher order side one bit at a time by one clock. Error detection is performed based upon whether the value R1 in the shift register SR when input of 32 bits of the encoded data ends coincides with the remaining 16 bits (parity bits) P1 of the input data string. A decoding method for detecting error based upon whether calculated parity coincides with parity that has been appended to an input data string, as described above, is referred to as a coincidence-detecting decoding method.                Second Prior-Art Example of Decoder (All-“0”s Detecting Decoding Method)        
In the CRC calculating unit shown in (B) of FIG. 43, the value in the register SR is made all “0”s in the initial state. The switch SW is switched to the A side, information bits of input data string W(x)′ are input successively and then the parity bits are input. Whether the value in the register SR when input of the parity bits ends is indicative of all “0”s is checked, it is determined that there is no error if all bits are “0”s and that there is an error if even one bit is “1”.
FIG. 46 illustrates the content of the register SR when encoded data that is the result of appending 16 parity bits to a 32-bit data string of all “1”s has been input to the EOR1 shown in (B) of FIG. 43 from the higher order side one bit at a time by one clock. Whether the value in the shift register SR when input of the 32 bits of encoded data and 16 parity bits ends is indicative of all “0”s is checked, it is determined that there is no error if all bits are “0”s and that there is an error if even one bit is “1”. A decoding method for determining that there is no error if all bits are “0”s and determining that there is an error if even one bit is “1”, as described above, is referred to as an all-“0”s-detecting method.
With CRC calculation, as indicated in FIGS. 44 to 46, calculation lasting at least the information bit length is required. That is, with the error-detecting encoder and decoder of FIGS. 44 to 46, at least 32 clocks are required. With a fourth-generation (new-generation) mobile communication system, the maximum information rate will be 100 Mbps or greater (1 Gbps or greater in case of a wireless LAN) according to the General Affairs Ministry. In the case of an information rate of 100 Mbps, a 100-MHz clock is necessary to perform the CRC calculation. In this case also there is a delay of one packet length brought about merely by CRC error detection. If resend control also is taken into account, there will be a marked decline in the data transmission rate since generating a resend-request signal takes time.
Further, if the CRC calculation employs a low-speed clock of, e.g., 25 MHz, four CRC calculation units will be required. Since a CRC calculation unit is intrinsically of small size, the scale of the hardware is not a problem but the delay due to calculation is a length of four packets. When resend is considered, the data transmission rate undergoes a large decline. FIG. 47 illustrates a time chart on the receiving side in such case. It will be understood that if a packet #1 is received and this packet is NG, then resend is requested from packet #7 onward. It should be noted that if the CRC calculation is performed at high speed, resend can be requested earlier.
Further, if the information rate is 1 Gbps, the delay ascribable to CRC calculation is ten packet lengths even when it is attempted to use ten CRC calculation circuits that operate at at 100-Mbps clock. Here resend control is not realistic.